package com.yun.algorithmproblem.leetcode;

import java.util.Arrays;

/**
 * 3292. 形成目标字符串需要的最少字符串数 II
 * <p>
 * 给你一个字符串数组 words 和一个字符串 target。
 * <p>
 * 如果字符串 x 是 words 中 任意 字符串的
 * 前缀
 * ，则认为 x 是一个 有效 字符串。
 * <p>
 * 现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。
 */
public class Leetcode3292 {

    public static void main(String[] args) {
        Leetcode3292 obj = new Leetcode3292();
        String[] words = new String[]{"abc","aaaaa","bcdef"};
        String target = "aabcdabc";
        int ans = obj.minValidStrings(words, target);
        System.out.println(ans);
    }

    public int minValidStrings(String[] words, String target) {
        int[] maxJump=new int[target.length()];
        for (String word : words) {
            String newWorld=word+'#'+target;
            int[] zF = zF(newWorld);
            for (int i = 0; i < target.length(); i++) {
                maxJump[i]=Math.max(maxJump[i],zF[i+word.length()+1]);
            }
        }
        return jump(maxJump);
    }

    public int[] zF(String s) {
        char[] sCharArray = s.toCharArray();
        int[] z = new int[s.length()];
        int l = 0, r = 0;
        z[0] = s.length();
        for (int i = 1; i < s.length(); i++) {
            if(z[i - l] < r - i){
                z[i] = z[i - l];
            }else {
                if(i<=r){
                    z[i] = r - i;
                }
                while (i + z[i] < s.length() && sCharArray[z[i]] == sCharArray[i + z[i]]) {
                    z[i]++;
                }
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }

    public int jump(int[] nums) {
        System.out.println(Arrays.toString(nums));
        int ans = 0;
        int curRight = 0;
        int nextRight = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == nextRight && nums[i] == 0) {
                return -1;
            }
            nextRight = Math.max(nextRight, i + nums[i]);
            if (i == curRight) {
                curRight = nextRight;
                ans++;
            }
        }
        return ans;
    }
}
